package com.qst.sort;

import java.util.Arrays;

/**
 * @author 刘汉平
 * @date 2019/9/10 15:11
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {3,1,7,4,5,6,9,2};
        mergeSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));

    }

    /**
     * @param nums 传入的数组
     * @param low 传入数组的开始位置
     * @param middle 传入数组的中间位置
     * @param hight 传入数组的末尾位置
     * 默认数组有序，把数组分成两个单独的数组，然后进行归并排序
     */
    public static void merge(int[] nums,int low,int middle,int hight){
        //用于存储归并后的临时数组
        int[] temp = new int[hight-low+1];
        //记录第一个数组遍历的起始位置
        int i = low;
        //记录第二个数组遍历的其实位置
        int j = middle+1;
        //用于记录在临时数组中存放的下标
        int index = 0;
        //遍历两个数组，取出小的数字放在临时数组中
        while (i<=middle&&j<=hight){
            //假如第一个数组的数字小，则把他存入临时数组中
            if (nums[i]<=nums[j]){
                temp[index] = nums[i];
                i++;
                //否则第二个数组中小的数放入临时数组中
            }else {
                temp[index] = nums[j];
                j++;
            }
            index++;
        }
        //处理剩余的数据
        while (j<=hight){
            temp[index] = nums[j];
            j++;
            index++;
        }
        while (i<=middle){
            temp[index] = nums[i];
            i++;
            index++;
        }
        //把临时数组中的数据重新存入原数组
        for (int k=0;k<temp.length;k++){
            nums[k+low] = temp[k];
        }
    }

    public static void mergeSort(int[] nums,int low,int high){
        if (low<high){
            int middle = (low+high)/2;
            mergeSort(nums,low,middle);
            mergeSort(nums,middle+1,high);
            merge(nums,low,middle,high);
        }
    }
}
